/FONT#0=NGR40L
␈↓
␈↓ ↓H

␈↓ ↓H
Outline for graduate reading and research: Lectures M-W, 10-12 
␈↓ ↓H

␈↓ ↓H
␈↓ αHSept 26
␈↓ ↓H

␈↓ ↓H
LISP data structures and functions: Sexprs and Mexprs.
␈↓ ↓H
␈↓ αHexamples: differentiation and representation problems.
␈↓ ↓H

␈↓ ↓H
␈↓ αH␈↓ βHthe domain
␈↓ ↓H
␈↓ αH␈↓ βH atoms and sexprs
␈↓ ↓H
␈↓ αH␈↓ βH representation as binary trees; `box notation'
␈↓ ↓H
␈↓ αH␈↓ βH list notation
␈↓ ↓H
␈↓ αH␈↓ βHthe functions
␈↓ ↓H
␈↓ αH␈↓ βH the primitive functions and composition
␈↓ ↓H
␈↓ αH␈↓ βH conditional expressions
␈↓ ↓H
␈↓ αH␈↓ βHevaluation by `intuition'
␈↓ ↓H
␈↓ αH␈↓ βHrecursive definitions
␈↓ ↓H
␈↓ αH␈↓ βH styles of definition
␈↓ ↓H
␈↓ αH␈↓ βHrepresentation of problems as LISP functions
␈↓ ↓H
␈↓ αH␈↓ βH rep. of domains as sexprs
␈↓ ↓H
␈↓ αH␈↓ βH rep. of problem as LISP functions
␈↓ ↓H
␈↓ αH␈↓ βH interrelations of representations
␈↓ ↓H
␈↓ αH␈↓ βHexamination of the differentiation algorithm for polys.
␈↓ ↓H
␈↓ αH␈↓ βH the algorithm is recursive
␈↓ ↓H
␈↓ αH␈↓ βH the domain (polys.) is well defined
␈↓ ↓H
␈↓ αH␈↓ βH rep. of domain as Sexprs.
␈↓ ↓H
␈↓ αH␈↓ βH rep of algorithm as  LISP fnc.
␈↓ ↓H
␈↓ αH␈↓ βH evaluation; algebraic simplification
␈↓ ↓H
␈↓ αH␈↓ βHreiteration of rep problem 
␈↓ ↓H

␈↓ ↓H
␈↓ αH␈↓ βH problem ==>LISP fnc |
␈↓ ↓H
␈↓ αH␈↓ βH␈↓ ∧H␈↓ ¬H     > evaluation ==> Sexpr ==> interpret
␈↓ ↓H
␈↓ αH␈↓ βH domain  ==> Sexprs  |␈↓ πH␈↓ λH␈↓ 	H␈↓ 
H  as answer
␈↓ ↓H

␈↓ ↓H
eval and friends: simple symbol tables and λ-expressionvs
␈↓ ↓H
␈↓ αHPrefix and postfix notations and their evaluators.
␈↓ ↓H
␈↓ αHthe label operator.
␈↓ ↓H
␈↓ αHfix-point vs. computation.
␈↓ ↓H

␈↓ ↓H
␈↓ αH␈↓ βHinvestigation of `evaluation by intuition'
␈↓ ↓H
␈↓ αH␈↓ βH call by value; call by name; other
␈↓ ↓H
␈↓ αH␈↓ βH meaning of variables
␈↓ ↓H
␈↓ αH␈↓ βH meaning of function definitions
␈↓ ↓H
␈↓ αH␈↓ βHevaluation can be described mechanically
␈↓ ↓H
␈↓ αH␈↓ βH evaluation is thus a problem expressible as LISP fnc.
␈↓ ↓H
␈↓ αH␈↓ βH the representation of LISP expressions as Sexprs.
␈↓ ↓H
␈↓ αH␈↓ βH intuitive description of eval by value.
␈↓ ↓H
␈↓ αH␈↓ βHdescription of eval for primitive fncs.- constant args
␈↓ ↓H
␈↓ αH␈↓ βH composition
␈↓ ↓H
␈↓ αH␈↓ βH conditionals
␈↓ ↓H
␈↓ αH␈↓ βHsimple symbol tables
␈↓ ↓H
␈↓ αH␈↓ βHextension of eval to variables
␈↓ ↓H
␈↓ αH␈↓ βHrepresentation of function definitions
␈↓ ↓H
␈↓ αH␈↓ βH the λ-notation: function names are variables
␈↓ ↓H
␈↓ αH␈↓ βHeval for λ.
␈↓ ↓H
␈↓ αH␈↓ βH detailed example of evaluation: 3!
␈↓ ↓H
␈↓ αH␈↓ βH problems with recursion
␈↓ ↓H
␈↓ αH␈↓ βHthe label operator.
␈↓ ↓H
␈↓ αH␈↓ βHfixpoints vs. computations: equality vs. assignment
␈↓ ↓H
␈↓ αH␈↓ βHother evaluation schemes and notations
␈↓ ↓H
␈↓ αH␈↓ βH prefix and postfix notation
␈↓ ↓H
␈↓ αH␈↓ βH evaluators and stacks
␈↓ ↓H
␈↓ αH␈↓ βHimportance of eval
␈↓ ↓H
␈↓ αH␈↓ βH semantics: Scott-LCF; Hoare-VCGEN; McCarthy-EVAL.
␈↓ ↓H
␈↓ αH␈↓ βH extensibility
␈↓ ↓H
␈↓ αH␈↓ βH parsing: Mexpr to Sexpr
␈↓ ↓H
␈↓ αH␈↓ βH why code in Sexprs?
␈↓ ↓H
␈↓ αH␈↓ βHMacros: why and how
␈↓ ↓H
␈↓ αH␈↓ βH extension of eval.
␈↓ ↓H

␈↓ ↓H
         October 3
␈↓ ↓H

␈↓ ↓H
Implementation of LISP: recursion and stacks, symbol tables and hashing and
␈↓ ↓H
  property lists, garbage collection
␈↓ ↓H
Miscellany on efficency, and LISP trickery.
␈↓ ↓H

␈↓ ↓H
␈↓ αH␈↓ βHon to the machine; 
␈↓ ↓H
␈↓ αH␈↓ βH the read-eval-print loop; 
␈↓ ↓H
␈↓ αH␈↓ βH the LISP machine(static and dynamic structure)
␈↓ ↓H
␈↓ αH␈↓ βHsymbol tables: predefine w.o. jamming symbol tables or
␈↓ ↓H
␈↓ αH␈↓ βH  redefining eval.
␈↓ ↓H
␈↓ αH␈↓ βHproperties of variables: name, value, function, funny function.
␈↓ ↓H
␈↓ αH␈↓ βH PNAME, VALUE, EXPR, FEXPR
␈↓ ↓H
␈↓ αH␈↓ βH property lists: atoms are special lists.
␈↓ ↓H
␈↓ αH␈↓ βH  goodbye binary trees, hello list-structure
␈↓ ↓H
␈↓ αH␈↓ βHhow lists are stored: unique atoms
␈↓ ↓H
␈↓ αH␈↓ βH where are they: free space and full word space.
␈↓ ↓H
␈↓ αH␈↓ βH who does it: read
␈↓ ↓H
␈↓ αH␈↓ βH how its done: hashing and the object list
␈↓ ↓H
␈↓ αH␈↓ βH why: implementation of eq and atom
␈↓ ↓H
␈↓ αH␈↓ βHmore detail on read.
␈↓ ↓H
␈↓ αH␈↓ βHa first look at cons: the garbage collector
␈↓ ↓H
␈↓ αH␈↓ βHreview of the static structure of the machine.
␈↓ ↓H
␈↓ αH␈↓ βHimplementation of eval
␈↓ ↓H
␈↓ αH␈↓ βH binding and the VALUE-cell:reconciliation with recursion
␈↓ ↓H
␈↓ αH␈↓ βH  alternatives
␈↓ ↓H
␈↓ αH␈↓ βHwhere garbage comes from
␈↓ ↓H
␈↓ αH␈↓ βH cons and the garbage collector revisited
␈↓ ↓H
␈↓ αH␈↓ βHimplementation of recursive calls: contour model.
␈↓ ↓H
␈↓ αH␈↓ βH contour for 3!
␈↓ ↓H
␈↓ αH␈↓ βH countour for simple block structure
␈↓ ↓H
␈↓ αH␈↓ βH stacks
␈↓ ↓H
␈↓ αH␈↓ βH stack model for simple block structure
␈↓ ↓H
␈↓ αH␈↓ βH stack model for 3!
␈↓ ↓H
␈↓ αH␈↓ βHLISP's list modifying functions: rplaca and rplacd.
␈↓ ↓H
␈↓ αH␈↓ βHefficiency; alternative schemes for:
␈↓ ↓H
␈↓ αH␈↓ βH storage of lists
␈↓ ↓H
␈↓ αH␈↓ βH traversal of lists
␈↓ ↓H
␈↓ αH␈↓ βH garbage collection
␈↓ ↓H
␈↓ αH␈↓ βHless complex data structures and their representation
␈↓ ↓H
␈↓ αH␈↓ βH arrays and strings
␈↓ ↓H
␈↓ αH␈↓ βH  mother vectors 
␈↓ ↓H
␈↓ αH␈↓ βH  string space, string operations, 
␈↓ ↓H
␈↓ αH␈↓ βH  compacting garbage collection
␈↓ ↓H
␈↓ αH␈↓ βH
␈↓ ↓H
␈↓ αHOctober 17
␈↓ ↓H

␈↓ ↓H
Compilation vs. evaluation, syntax-directed processes, PDP-10.
␈↓ ↓H
  prefix, infix, and postfix revisited
␈↓ ↓H
  Compilers for subsets of LISP
␈↓ ↓H
  Correctness and equivalence results for compilers and interpreters.
␈↓ ↓H

␈↓ ↓H
␈↓ αH␈↓ βHsimple stack machine for simple function evaluation
␈↓ ↓H
␈↓ αH␈↓ βH  j[x,y] <= f[g[x];h[y]]
␈↓ ↓H
␈↓ αH␈↓ βHmore precise description of the calling conventions;
␈↓ ↓H
␈↓ αH␈↓ βHmechanization of the code generation: compilation.
␈↓ ↓H
␈↓ αH␈↓ βHmore detailed machine for function calls: PDP-10
␈↓ ↓H
␈↓ αH␈↓ βHcompiler for LISP subset: functions with constant args.
␈↓ ↓H
␈↓ αH␈↓ βHsyntax-directed proccesses.
␈↓ ↓H
␈↓ αH␈↓ βH BNF definitions; analytic vs. synthetic grammars.
␈↓ ↓H
␈↓ αH␈↓ βH BNF for simple arithmetic expressions.
␈↓ ↓H
␈↓ αH␈↓ βH associated semantics for infix to postfix translator.
␈↓ ↓H
␈↓ αH␈↓ βH associated sematics for evaluation.
␈↓ ↓H
␈↓ αH␈↓ βH associated semantics for compilation on single address machine.
␈↓ ↓H
␈↓ αH␈↓ βHBNF for  LISP subset and semantics for compilation.
␈↓ ↓H
␈↓ αH␈↓ βHBNF for LISP subset+conditionals:
␈↓ ↓H
␈↓ αH␈↓ βH how to write code for it.
␈↓ ↓H
␈↓ αH␈↓ βH how to associate semantics.
␈↓ ↓H
␈↓ αH␈↓ βHAssemblers
␈↓ ↓H
␈↓ αH␈↓ βH two pass
␈↓ ↓H
␈↓ αH␈↓ βH one pass, forward references and fix-ups.
␈↓ ↓H
␈↓ αH␈↓ βHBNF for above subsets with variables(λ-expressions).
␈↓ ↓H
␈↓ αH␈↓ βH associated semantics.
␈↓ ↓H
␈↓ αH␈↓ βHcompiling algorithms for variable access.
␈↓ ↓H
␈↓ αH␈↓ βH global variables and intercommunication with interpreted
␈↓ ↓H
␈↓ αH␈↓ βH  functions.
␈↓ ↓H
␈↓ αH␈↓ βH function calls and tracing
␈↓ ↓H
␈↓ αH␈↓ βHLondon's paper.
␈↓ ↓H

␈↓ ↓H
␈↓ αHNovember 5
␈↓ ↓H
Control structures: Block structure, contour model, implementation.
␈↓ ↓H
  LISP progs: assignment and iteration in LISP.
␈↓ ↓H
  Functional arguments. Bobrow-Wegbreit primitives and CONNIVER.
␈↓ ↓H
  Call by value, reference, and name.
␈↓ ↓H
  Models of implementation for ALGOL and EULER: retention vs. deletion
␈↓ ↓H
   static and dynamic chains; the display
␈↓ ↓H
   pointer-, label-, and procedure-valued variables
␈↓ ↓H
  Backtracking and PLANNER.
␈↓ ↓H

␈↓ ↓H
␈↓ αHNov 21
␈↓ ↓H

␈↓ ↓H
Abstract and concrete syntax: VDL and LISP. Extensibility: ECL. 
␈↓ ↓H
  Grammars: precedence and LR(k).
␈↓ ↓H
  Parsing techniques: top down, bottom up, Euler, Knuth, Floyd.
␈↓ ↓H
   Cheatham's dominoes.
␈↓ ↓H
  Quam's SDIO, MLISP2's parser.
␈↓ ↓H

␈↓ ↓H
␈↓ αHDec 11
␈↓ ↓H

␈↓ ↓H
Machines and systems: Machine organization and systems design.
␈↓ ↓H
  Burroughs machines.
␈↓ ↓H
  Multi-programming and -processing, time sharing and requisite
␈↓ ↓H
   hardware and software.
␈↓ ↓H
  Contour model and Bobrow-Wegbreit again: OREGANO
␈↓ ↓H
   coroutines, events, interrupts, and tasks.
␈↓ ↓H

␈↓ ↓H
␈↓ αHJan 1
␈↓ ↓H

␈↓ ↓H
The world ends
␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
Miscellaneous topics
␈↓ ↓H
  structured programming
␈↓ ↓H
  applications to A.I.
␈↓ ↓H
  Data bases a la PLANNER and CONNIVER.
␈↓ ↓H
Introduction
␈↓ ↓H
The central thesis of these notes is that LISP is the most natural
␈↓ ↓H
language and formalism with which to begin the study of Computer
␈↓ ↓H
Science.  Skepticism should be the appropriate response to the preceeding,
␈↓ ↓H
but we hope to convince you of the eternal truth of that statement by the
␈↓ ↓H
time these notes are completed.
␈↓ ↓H

␈↓ ↓H
The structure of the notes  is the following: First the basics of the
␈↓ ↓H
language are introduced. The domain of interest is called Symbolic expressions
␈↓ ↓H
or S-expressions or more frugally, sexprs.  Then the primitive functions
␈↓ ↓H
operating on this domain arrive and finally functional composition 
␈↓ ↓H
and conditional expressions ("if-then-else" ) are given as tools to combine
␈↓ ↓H
the primitives. So far everything is very mathematical and precise. However
␈↓ ↓H
LISP indeed is a tool of the Computer Scientist, for we shall then see that
␈↓ ↓H
common non-numerical algorithms have a NATURAL interpretation as LISP functions
␈↓ ↓H
(operation on Sexprs).  For example, a common non numerical algorithm is the
␈↓ ↓H
manipulation of polynominals-- addition , subtraction and multiplication.
␈↓ ↓H
We will give (many) representations of polynominals as sexprs and then will
␈↓ ↓H
show that there are very intuitive LISP functions which codify the intuitive
␈↓ ↓H
operations of manipulations of polynominals.  The advantages of using a
␈↓ ↓H
high level language for numerical algorithms is well-known. LISP simply
␈↓ ↓H
extends these benefits to the non-numerical algorithms.
␈↓ ↓H
The only criteria for writing LISP functions  are two: find a representation
␈↓ ↓H
of the domain  as Sexprs; be able to describe the operations which you
␈↓ ↓H
wish to perform on this domain in a mechanical manner (i.e., as algorithms)
␈↓ ↓H

␈↓ ↓H
We then look at perhaps the most interesting algorithms in Computer Science:
␈↓ ↓H
We notice that the process which is commonly used by humans in the evaluation
␈↓ ↓H
of functional composition is very mechanical. For example, most people
␈↓ ↓H
when asked to evaluate (1+2)*(3+4) reduce the problem to 3*7 and then to 21.
␈↓ ↓H
We  notice that the other artifacts of LISP algorithms also have mechanical
␈↓ ↓H
evaluation. We thus have an intuitive description of the evaluation process
␈↓ ↓H
used in evaluating LISP functions applied to Sexpr arguments.  We thus
␈↓ ↓H
have satisfied one of the above criteria for writing LISP funtions. We then 
␈↓ ↓H
show how to satisfy the other criteria: reprentation of the domain (LISP
␈↓ ↓H
functions applied to arguments) as Sexprs.  When this is accomplished
␈↓ ↓H
we can write a LISP function which describes the LISP evaluation process.
␈↓ ↓H

␈↓ ↓H
The consequences of this (rather incestuous) process contain some of the
␈↓ ↓H
most beautiful results in the field. A good portion to the remaining notes
␈↓ ↓H
explore these consequences: clarification of programming language semantics,
␈↓ ↓H
and an extraordinary clear view of evaluation and compilation are only a
␈↓ ↓H
couple of the benefits. Another segment of the notes deals with the 
␈↓ ↓H
implementation of LISP: almost all the tools of language implementation
␈↓ ↓H
appear in the implementation of LISP. Indeed, many of them have there 
␈↓ ↓H
origins in LISP. As you might expect, much of the implementation can be
␈↓ ↓H
described as LISP functions.
␈↓ ↓H

␈↓ ↓H
These two strands: the descrption of evaluation and compilation, and
␈↓ ↓H
the implementation are not separated in the notes for the good reason
␈↓ ↓H
that concepts are closely intertwined. Programming languages must not be
␈↓ ↓H
designed, described or otherwise advertised, independently of their
␈↓ ↓H
implementation. The final section of the notes is related to this: the
␈↓ ↓H
design of machines for efficient language implementation.
␈↓ ↓H

␈↓ ↓H

␈↓ ↓H